
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution
{
public:
    int widthOfBinaryTree1(TreeNode* root)
    {
        int res = 0;
        vector<pair<TreeNode*, unsigned int>> v;
        vector<pair<TreeNode*, unsigned int>> tmp;

        for (v.push_back({ root, 0 }); v.size();)
        {
            res = max((unsigned int)res, v.back().second - v.front().second + 1);

            tmp.clear();
            for (const auto& [x, y] : v)
            {
                if (x->left)
                    tmp.push_back({ x->left, 2 * y + 1 });
                if (x->right)
                    tmp.push_back({ x->right, 2 * y + 2 });
            }
            v = tmp;
        }

        return res;
    }

    int widthOfBinaryTree2(TreeNode* root)
    {
        int res = 1;
        queue<pair<TreeNode*, unsigned long long>> q;
        q.push({ root, 0 });

        for (unsigned long long beg = 0, end = 0; q.size();)
        {
            beg = q.front().second;

            for (int n = q.size(); n; --n)
            {
                if (1 == n)
                    end = q.front().second;

                TreeNode* front = q.front().first;
                unsigned long long index = q.front().second;

                q.pop();
                if (front->left)
                    q.push({ front->left, 2 * index + 1 });
                if (front->right)
                    q.push({ front->right, 2 * index + 2 });
            }

            res = (int)max((unsigned long long)res, end - beg + 1);
        }

        return res;
    }
};

int main()
{



	return 0;
}